public class Sort {

    public static void main(String[] args) {
        int[] array = {1,5,8,7,2,1};
        mergeSort(array, 0, array.length -1);

        for(int i : array)
        System.out.println("Result 1 " + i);


        int[] array2 = {1,5,8,7,2,1};
        quickSort(array2, 0, array2.length -1);

        for(int i : array2)
        System.out.println("Result 2 " + i);
    }

    public static void mergeSort(int[] array, int lo, int hi) {

        if (hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        mergeSort(array, lo, mid);
        mergeSort(array,mid+1, hi);
        merge(array, lo, mid, hi);
    }

    public static void merge(int[] array, int lo, int mid, int hi) {

        int[] aux = new int[hi - lo+ 1];
        int i = lo, j = mid + 1, k = 0;

        while (i <= mid && j <= hi) {
            aux[k++] = array[i] < array[j] ? array[i++] : array[j++];
        }

        while (i <= mid) aux[k++] = array[i++];
        while (j <= hi) aux[k++] = array[j++];

        for (int p = 0; p < aux.length; p++) {
            array[lo + p] = aux[p];
        }
    }

    public static void quickSort(int[] array, int lo, int hi) {

        if (hi <= lo) return;
        int j = partition(array, lo, hi);
        quickSort(array, lo, j - 1);
        quickSort(array, j + 1, hi);
    }

    public static int partition(int[] array, int lo, int hi) {

        int pivot = array[lo];     
        int i = lo, j = hi + 1;

        while (true) {
            while (array[++i] < pivot) if (i == hi) break;
            while (pivot < array[--j]) if (j == lo) break;
            if (i >= j) break;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        int temp = array[j];
        array[j] = pivot;
        array[lo] = temp;

        return j;
    }
    
}